# -*-* encoding:UTF-8 -*-
# author            : mengy
# date              : 2018/12/25
# python-version    : Python 3.7.0
# description       : python学习算法--递归

# 求解阶乘
def factorial(i):
    """
    用递归的方式实现求阶乘 \n
    时间复杂度为: O(n) \n
    :param i:
    :return:
    """
    if i < 0:
        print('负数没有阶乘')
        return
    elif i == 0 or i == 1:
        return 1
    return i * factorial(i - 1)


def factorial_loop(i):
    """
    用循环的方式实现求阶乘 \n
    时间复杂度为: O(n) \n
    :param i:
    :return:
    """
    if i < 0:
        print('负数没有阶乘')
        return
    elif i == 0 or i == 1:
        return 1
    value = 1
    while i > 1:
        value *= i
        i -= 1
    return value


#   求解斐波拉契数列
#   0 1 1 2 3 5 8 13 21 34 55 89...
def fibonacci(n):
    """
    用递归的方式求解斐波拉契数列 \n
    递归表达式:
                  F(n) = {  1                   <n = 1>     T(n) = 1 \n
                            1                   <n = 2>     T(n) = 1\n
                            F(n-1) + F(n-2)     <n > 2>     T(n) = T(n-1) + T(n-2) \n
    时间复杂度为: O(2^n)
    :param n:
    :return:
    """
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)


def fibonacci_loop(n):
    """
    用循环的方式求解斐波拉契数列 \n
    时间复杂度为: O(n)
    :param n:
    :return:
    """
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        a, b = 0, 1
        for i in range(n):
            a, b = b, a + b
        return a


if __name__ == '__main__':
    # print(factorial(-1))
    # print(factorial_loop(-1))

    print(fibonacci(25))
    print(fibonacci_loop(25))
